import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/10 17:10
 * @description 暴力搜索和 字典树都会超时，可使用字符串hash来判断两个子字符串是否相等
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.sumScores("babab");
    }

    int n = (int) 1e5 + 10;
    long[] h;
    long[] p;
    int P = 13131;

    public long sumScores(String s) {
        h = new long[n];
        p = new long[n];
        p[0] = 1;
        for (int i = 0; i < s.length(); i++) {
            h[i + 1] = h[i] * P + s.charAt(i);
            p[i + 1] = p[i] * P;
        }
        //h[i] 前i个
        long res = 0;
        //枚举后缀多少个
        for (int i = 1; i <= s.length(); i++) {
            int start = s.length() - i;
            int l = 0;
            int r = i;
            while (l < r) {
                int mid = (l + r + 1) / 2;
                //枚举最长前缀的长度
                long v1 = get(start, start + mid - 1);
                long v2 = get(0, mid - 1);
                if (v1 == v2) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            //get l 表示长度
            res += l;
        }
        return res;
    }

    public long get(int a, int b) {
        return h[b + 1] - h[a] * p[b - a + 1];
    }
}
